import java.util.*;
import java.lang.*;
public class Test {
    public static List<String> topKFrequent(String[] words, int k) {

        //找出前k个高频单词
        HashMap<String, Integer> map = new HashMap<>();
        for(String word : words){
            if(map.get(word) == null){
                map.put(word, 1);
            }else{
                int time = map.get(word);
                map.put(word, time+1);
            }
        }

        //创建小根堆
        PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(heap.size() < k){
                heap.offer(entry);
            }else{
                Map.Entry<String, Integer> top = heap.peek();
                //如果堆顶元素的value小于entry中的元素
                if(top.getValue().compareTo(entry.getValue()) < 0){
                    heap.poll();
                    heap.offer(entry);
                }
                //二者相等时比较key的大小
                else if(top.getValue().compareTo(entry.getValue()) == 0){
                    if(top.getKey().compareTo(entry.getKey()) > 0){
                        heap.poll();
                        heap.offer(entry);
                    }
                }
            }
        }

        //依次弹出堆顶元素，存放在list中
        List<String> list = new ArrayList<>();
        for(int i = 0; i < k; i++){
            Map.Entry<String, Integer> entry = heap.poll();
            list.add(entry.getKey());
        }

        //转置集合
        Collections.reverse(list);
        return list;
    }
    public static void main(String[] args) {
        int k = 2;
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> list = new ArrayList<>();
        list = topKFrequent(words,k);
        System.out.println(list);
    }
}
